package Algorithm.string;

/**
 * @Desc:   字符串相乘
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
 *          输入: num1 = "2", num2 = "3"
 *          输出: "6"
 *          输入: num1 = "123", num2 = "456"
 *          输出: "56088"
 *
 *          num1 和 num2 的长度小于110。
 *          num1 和 num2 只包含数字 0-9。
 *          num1 和 num2 均不以零开头，除非是数字 0 本身。
 *          不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
 *
 *  https://leetcode-cn.com/problems/multiply-strings/
 * @author: cww
 * @DateTime: 2020/3/31 13:40
 */

public class MultiplyStr {
    public static void main(String[] args) {
        System.out.print(multiply("123","12"));
    }

    /**
     * 思想：把两个数放入数组，用传统的手算方式
     *      例 1234*25
     *      value | value[0] | value[1] | value[2] | value[3] | value[4] | value[5] |
     *      num1  |          |          | num[0]=1 | num[1]=2 | num[2]=3 | num[3]=4 |
     *      num2  |          |          |          |          | num[0]=2 | num[1]=5 |
     *                       |          |  1*5=5   |  2*5=10  |  3*5=15  |  4*5=20  |
     *                       |  1*2=2   |  2*2=4   |  2*3=6   |  2*4=8   |          |
     *                       |    2     |    9     |    16    |    23    |    20    | 位处理前
     *                       |    3     |    0     |    8     |     5    |     0    | 位处理后：每一位除10的商加到上一位，当前位取余数
     *     最后处理掉高位中为 0 的数字位
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply(String num1, String num2){
        if("0".equals(num1)||"0".equals(num2)) return "0";
        int[] value = new int[num1.length()+num2.length()];
        // 竖式乘法的计算累加
        for(int i=num1.length()-1;i>=0;i--){
            for(int j=num2.length()-1;j>=0;j--){
                value[i+j+1] += (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
            }
        }
        // 处理进位
        int temp = 0;
        for(int i=value.length-1;i>=0;i--){
            value[i] += temp;
            temp = value[i]/10;
            value[i] %= 10;
        }
        // 处理头部的0，返回结果
        StringBuilder sb = new StringBuilder();
        boolean start = true;
        for(int i=0;i<value.length;i++){
            if(value[i]==0 && start){
                continue;
            } else{
                start = false;
                sb.append(value[i]);
            }
        }
        return sb.toString();
    }

}
